package com.captain.leetcode.链表;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * Des:
 *
 * @author XL
 * @Date 2021/8/17 11:48
 */
public class LRUCache {

    //给定容量 , 被访问了就移动到head , 超过容量则删除末尾数据
    //双端队列 + hashMap结构

    //链表中的数量
    private int size;
    //最大容量 : 超过容量 移除末尾的元素
    private int capacity;
    //map作为缓存, 快速取出数据
    private Map<Integer, BidirectionalNode> cache = new HashMap<>();
    //双向链表
    private BidirectionalNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new BidirectionalNode();
        tail = new BidirectionalNode();
        //构成双向链表
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        BidirectionalNode node = cache.get(key);
        if (node == null) return -1;
        //访问一下移动到头部
        moveToHead(node);
        return node.value;
    }

    //如果key 不存在, 则存到最前面,如果存在,则更新值, 并移动到最前面
    public void put(int key, int value) {
        BidirectionalNode nd = cache.get(key);
        if (Objects.isNull(nd)) {
            //创建新的节点
            BidirectionalNode bdNode = new BidirectionalNode(key, value);
            //存储缓存
            cache.put(key, bdNode);
            //添加到头部
            addHead(bdNode);
            size++;
            if (size > capacity) {
                //删除尾部节点
                BidirectionalNode tail = removeTailNode();
                cache.remove(tail.key);
                size--;
            }
            return;
        }
        //存在
        nd.value = value;
        //移动到头部
        moveToHead(nd);
    }

    private void moveToHead(BidirectionalNode nd) {
        //删除节点
        removeNode(nd);
        //添加到头部
        addHead(nd);
    }

    private BidirectionalNode removeTailNode() {
        BidirectionalNode res = tail.prev;
        removeNode(res);
        return res;
    }

    /**
     * des:
     * 删除节点
     *
     * @param node 删除节点
     * @return {@link }
     * @author captain
     * @date 2021/8/17 13:13
     */
    private void removeNode(BidirectionalNode node) {
        //next指针
        node.prev.next = node.next;
        //prev指针
        node.next.prev = node.prev;
    }

    /**
     * des:
     * 添加节点数据到头部
     *
     * @param nn 节点
     * @return {@link}
     * @author captain
     * @date 2021/8/17 12:36
     */
    private void addHead(BidirectionalNode nn) {
        //处理next指针
        nn.next = head.next;
        head.next = nn;

        //处理prev指针
        nn.prev = head;
        nn.next.prev = nn;
    }

    public static class BidirectionalNode {
        int key;
        int value;
        BidirectionalNode prev;
        BidirectionalNode next;

        public BidirectionalNode() {
        }

        public BidirectionalNode(int key, int value) {
            this.key = key;
            this.value = value;

        }
    }
}
